//
//  35.数组中的逆序对.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/24.
//

import Foundation
/*
 题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
      对于50%的数据,size <= 10^4
      对于75%的数据,size <= 10^5
      对于100%的数据,size <= 2 * 10^4
  
 思路1：暴⼒解法，顺序扫描整个数组，每扫描到⼀个数字的时候，逐个⽐较该数字和它后⾯的数字的⼤⼩。如果后⾯的数字⽐它⼩，则这两个数字就 成⼀个逆序对。假设数组中含有n个数字，由于每个数字都要和O(n)个数字作⽐较，因此这个算法的时间复杂度是O(n^2)。
 思路2：分治思想，采⽤归并排序的思路来处理O(nlogn)，递归法
 思路3：分治思想，采⽤归并排序的思路来处理O(nlogn)，迭代法
 */
func offer_35() {
    print(Solution().InversePairs3([1,2,3,4,5,6,7,0]))
}

fileprivate class Solution {
    func InversePairs1(_ data: [Int]) -> Int {
        var count = 0
        for i in 0..<data.count {
            for j in i+1..<data.count {
                if data[i] > data[j] {
                    count += 1
                }
            }
        }
        return count % 1000000007
    }
    
    func InversePairs2(_ data: [Int]) -> Int {
        guard data.count > 1 else { return 0 }
        var data = data
        var count = 0
        func mergeSort(_ arr: inout [Int], _ start: Int, _ end: Int) {
            guard start < end else { return }
            func merge(_ arr: inout [Int], _ start: Int, _ mid: Int, _ end: Int) {
                var mergeArr = [Int]()
                var a = start, b = mid + 1
                while a <= mid && b <= end {
                    if arr[a] <= arr[b] {
                        mergeArr.append(arr[a])
                        a += 1
                    } else {
                        mergeArr.append(arr[b])
                        b += 1
                        //如果前面的元素大于后面的，那么在前面元素之后的元素都能和后面的元素构成逆序对
                        count += mid-a+1
                    }
                }
                while a <= mid {
                    mergeArr.append(arr[a])
                    a += 1
                }
                while b <= end {
                    mergeArr.append(arr[b])
                    b += 1
                }
                arr.replaceSubrange(start...end, with: mergeArr)
            }
            let mid = (start + end) / 2
            mergeSort(&arr, start, mid)
            mergeSort(&arr, mid+1, end)
            merge(&arr, start, mid, end)
        }
        mergeSort(&data, 0, data.count-1)
        print(data)
        return count % 1000000007
    }
    
    func InversePairs3(_ data: [Int]) -> Int {
        guard data.count > 1 else { return 0 }
        var data = data
        var count = 0
        func merge(_ arr: inout [Int], _ start: Int, _ mid: Int, _ end: Int) {
            var mergeArr = [Int]()
            var a = start, b = mid + 1
            while a <= mid && b <= end {
                if arr[a] <= arr[b] {
                    mergeArr.append(arr[a])
                    a += 1
                } else {
                    mergeArr.append(arr[b])
                    b += 1
                    //如果前面的元素大于后面的，那么在前面元素之后的元素都能和后面的元素构成逆序对
                    count += mid-a+1
                }
            }
            while a <= mid {
                mergeArr.append(arr[a])
                a += 1
            }
            while b <= end {
                mergeArr.append(arr[b])
                b += 1
            }
            arr.replaceSubrange(start...end, with: mergeArr)
        }
        
        // 迭代法
        let n = data.count
        /**
         * 迭代的方式是自底而上，递归是自顶向下
         * sz 是每次左右部分中元素的个数
         * 外层循环控制分组
         * 内层循环控制归并
         */
        var size = 1
        while size < n {
            var i = 0
            while i < n-size {
                // 将l...r分成两段，终点为mid
                let l = i, mid = i+size-1, r = min(i+2*size-1, n-1)
                // 对于arr[mid] <= arr[mid+1]的情况,不需要merge，因为是连续的
                if data[mid] > data[mid+1] {
                    merge(&data, l, mid, r)
                }
                i += size*2
            }
            size *= 2
        }
        print(data)
        return count % 1000000007
    }
}

